package com.future;

/**
 * Description: 80. 删除有序数组中的重复项 II
 * <p>
 * 输入：nums = [1,1,1,2,2,3]
 * 输出：5, nums = [1,1,2,2,3]
 *
 * @author weiruibai.vendor
 * Date: 2022/9/14 09:22
 */
public class Solution_80_II {

    public static void main(String[] args) {
        int[] nums = new int[]{1, 2, 2, 2, 2, 2, 4, 4, 4};
        nums = new int[]{1, 1, 1, 1, 2, 2, 2, 2, 2, 4, 4, 4};

        //System.out.println(removeDuplicates(nums));
        System.out.println(removeKDuplicates(nums, 3));
        System.out.println(removeDuplicatesItem(nums));
    }

    /**
     * @param nums
     * @return
     */
    public static int removeDuplicates(int[] nums) {
        int k = 2;
        return removeKDuplicates(nums, k);
    }

    /**
     * 通用方法
     * 给你一个有序数组 nums ，请你 原地 删除重复出现k次的元素，使得出现次数超过k次的元素只出现k次 ，返回删除后数组的新长度。
     * <p>
     * eg {1,1,1,1,1,2,2,2,2,3,4,4,5} k=3
     * 那么应该返 9, {1,1,1,2,2,2,4,4,5}
     *
     * @param nums
     * @param k
     * @return
     */
    private static int removeKDuplicates(int[] nums, int k) {

        if (nums.length <= k) {
            return nums.length;
        }

        int length = k;// 表示整理后的数组长度，那么有效下标最大长度是length-1

        for (int i = k; i < nums.length; i++) {

            /**
             * 1、当nums[i] == nums[index - 2] 说明 index-2,index-1,...,i都是相等的，需要跳过i位置的数
             * 2、说明此时长度为length的数组已经整理好，即[0,...,length-1]都符合题目了
             * 3、因为在下标length-2,..,i上是递增的，所以当nums[i] != nums[length - 2]，
             * 至少能保证不会存在超过2个相同的数，也有可能nums[length-1]=nums[i]，但是这个可以满足相同元素为个数为2
             */
            if (nums[i] != nums[length - k]) {
                /**
                 * 注意：
                 */
                nums[length++] = nums[i];
            }
        }
        return length;
    }

    /**
     * 删除重复的，返回数组最新长度
     *
     * @param nums
     * @return
     */
    private static int removeDuplicatesItem(int[] nums) {
        if (nums.length < 2) {
            return nums.length;
        }
        int L = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[L - 1] != nums[i]) {
                nums[L++] = nums[i];
            }
        }
        return L;
    }

}
